网络流总结&做题记录

网络流 24 题

总结一下套路:

1.二分图

二分图对偶定理

二分图最大权匹配 == 二分图最小点权覆盖 == w|∑w| - 二分图最大点权独立集

1.最小点权覆盖

将二分图的两部分分别与源点/汇点连容量为点权的边,二分图内部的边容量设为 ++\infty

最后图的最小割即为原二分图的最小点权覆盖。


考虑这样做的正确性:

二分图的点覆盖中每条边都至少被一个点覆盖,所以没有源点到汇点的路径,是新图的割。

新图的割的边集只可能包含源点与汇点为顶点的边(内部的边容量为 ++\infty),那么割掉一条边对应选出这个点。

2.最大点权独立集

由对偶定理和 1. 易得解法,不再赘述。

2.集合划分问题

将元素划分为两个集合 A,BA,B , 满足 AB=UA \cup B = UAB=A \cap B = \varnothing

划分的代价为:

iAai+iBbi\sum_{i \in A}a_i+\sum_{i \in B}b_i

同时给定一些关系,若元素 u,vu,v 不在同一集合则会有 wiw_i 的代价。

求划分的最小代价。


将一个元素拆成两个点,分别表示选入 A/BA/B 集合。再从源点/汇点向两部分的点连容量为 bi/aib_i/a_i 的边(注意容量是反的)。

元素之间的代价可视为 (Au,Bv)/(Av,Bu)(A_u,B_v)/(A_v,B_u) 之间连容量为 wiw_i 的边。

当然,为了使 uu 被至少被一个集合选中,在 (Au,Bu)(A_u,B_u) 之间连容量为 ++\infty 的边。

图的最小割即为最小代价。


正确性?

因为 (Au,Bu)(A_u,B_u) 之间的边容量为 ++\infty , 不可能是原图的边割集。

所以 Au,BuA_u,B_u 之中一定有一点与源汇的边被割去,若 (S,Au)(S,A_u) 被割则表示选入 BB 集合,反之若 (Bu,T)(B_u,T) 被割则选入 AA 集合。这也解释了建图时容量是相反的。

(Au,Bv),(Av,Bu)(A_u,B_v),(A_v,B_u) 被割则表示接受 wiw_i 的代价,显然 (Au,Bv),(Av,Bu)(A_u,B_v),(A_v,B_u)
22 条边只会被割 11 条。

可以看出,图的割便是一个选择方案,选择方案也对应一个割。求出最小割即可。

eg.\text{eg.} P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

3.方格问题

  • 格子之间有要求

格点之间的要求视作边,若是二分图则是最大点权独立集。

eg.\text{eg.} P2774 方格取数问题    ~~~ P3355 骑士共存问题

  • 每行、每列、每个格子有要求

对于每行、每列分别建一个点

行与列之间的边对应格子限制,源点与行的边 / 汇点与列的边 对应 行 / 列 的限制。

值得注意的是,这个图也是一个二分图。

eg.\text{eg.} P4311 士兵占领    ~~~ P4194 矩阵

4.最大权闭合子图

5.最大密度子图


2020.12.18 拆点、最大流

P3153 [CQOI2009]跳舞

二分答案 + 拆点 + 最大流

P3163 [CQOI2014]危桥

最大流

2020.12.19 最大流/最小割

SP839 Optimal Marks

按位考虑 + 最小割

2020.12.21 上下界网络流

P4311 士兵占领

P4843 清理雪道

UVA1440 Inspection

2020.12.22 上下界网络流

P4194 矩阵

2020.12.23 拆点、最大流

UVA12125 March of the Penguins

拆点

SP4063 Sell Pigs

最大流建模

2020.12.24 最大流/最小割

P1344 [USACO4.4]Pollutant Control

特殊处理:

在最小割最小的前提下,让割的边最少。

对每一条 (u,v,c)(u,v,c) 的边变为 (u,v,c×base+1)(u,v,c \times base+1)(base>m)(base > m)

最后 Maxflow/base\text{Maxflow} /base 为最小割, Maxflow%base\text{Maxflow}\%base 为最少边。

P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

最小割建模

2020.12.25 最小割

UVA1660 Cable TV Network & SP300 Cable TV Network

最小割建模

P4662 [BalticOI 2008]黑手党

最小割建模

P3191 [HNOI2007]紧急疏散

最大流建模